package test.sort;

public class SortUtil {
	/**
	 * 冒泡排序实现-普通版
	 * 
	 * @param arr
	 */
	public static void bubbleSort(int[] arr) {
		// 如果数组为空，或是数组长度<=1，则不需要排序
		if (arr == null || arr.length <= 1) {
			return;
		}
		int len = arr.length;
		// 外层循环控制比较轮次，内层循环负责每一轮的具体两两比较
		for (int i = 0; i < len - 1; i++) {
			// 具体一轮当中的两元素比较
			for (int j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
					int temp = arr[j + 1]; // 元素交换
					arr[j + 1] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}

	/**
	 * 冒泡排序实现-优化版
	 * 
	 * @param arr
	 */
	public static void bubbleSortV2(int[] arr) {
		// 如果数组为空，或是数组长度<=1，则不需要排序
		if (arr == null || arr.length <= 1) {
			return;
		}
		int len = arr.length;
		// 设置是否发生交换的标志位
		boolean isSwapFlag;
		// 外层循环控制比较轮次，内层循环负责每一轮的具体两两比较
		for (int i = 0; i < len - 1; i++) {
			// 每轮开始时进行复位为false，相当于没有发生
			isSwapFlag = false;
			// 具体一轮当中的两元素比较
			for (int j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
					int temp = arr[j + 1]; // 元素交换
					arr[j + 1] = arr[j];
					arr[j] = temp;
					// 执行到这里说明已经发生交换，故设置为true
					isSwapFlag = true;
				}
			}

			/**
			 * 每比较完一轮，检查该轮比较是否发生位置调换,如果没有发生则说明整体已经有序，停止比较，如果发生了，则需要继续进行下一轮
			 */
			if (!isSwapFlag) {
				return;
			}
		}
	}

	public static void main(String[] args) {
		int[] intArray = { 9, 8, 7, 10, 1, 3, 5 };
		// bubbleSort(intArray);
		bubbleSortV2(intArray);

		for (int i : intArray) {
			System.out.println(i);
		}
	}
}
